//
// Created by yangchao on 2022/6/19.
// 207. 课程表: https://leetcode.cn/problems/course-schedule/
//
#include <vector>
#include <queue>
using namespace std;

class CanFinish {
public:
    bool canFinish(int numCourses, vector<vector<int>>& prerequisites) {
        //统计课程安排表中每个节点的入度
        vector<int> indegrees(numCourses);
        vector<vector<int>> adjacency(numCourses); ////邻接表
        queue<int> qe;

        for (const auto &pq : prerequisites) {
            //统计课程表安排图中每个节点的入度
            indegrees[pq[0]]++;
            //为邻接表赋值：索引[1]对应的节点为有向边的起点，[0]为终点
            //邻接表中的链表记录的是终点信息
            adjacency[pq[1]].push_back(pq[0]);
        }

        //将所有入度为0的节点入列
        for (int i = 0; i < numCourses; ++i) {
            if (indegrees[i] == 0) {
                qe.push(i);
            }
        }

        while (!qe.empty()) {
            //当qe非空时，依次将队首节点出队，在课程表安排图中删除此节点pre
            int pre = qe.front();
            qe.pop();
            numCourses--;
            //遍历pre的邻接节点【有向边的终点】
            for (const auto &cur : adjacency[pre]) {
                indegrees[cur]--;
                if (indegrees[cur] == 0) {
                    //cur的所有前驱节点已经删除，入度为0，将其重新入队列
                    qe.push(cur);
                }
            }
        }
        //若课程表有环，一定有节点的入度始终不为0
        return numCourses == 0;
    }
};

